// https://leetcode.cn/problems/add-binary/

#include <string>
#include <iostream>
#include <bitset>

using namespace std;

class Solution {
public:
    string addBinary(string a, string b) {
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		string bigStr = a;
		string smallStr = b;
		if(a.size() < b.size()){
			bigStr = b;
			smallStr = a;
		}
		int smallLen = smallStr.size();
		int bigLen = bigStr.size();

		int flag = 0;
		for(int i = 0; i < bigLen; i++){
			int tmp = 0;
			if(i < smallLen){
				tmp = (smallStr[i] - '0') + (bigStr[i] - '0') + flag;
			} else{
				tmp = (bigStr[i] - '0') + flag;
			}
			
			if(tmp >= 2){
				flag = 1;
			}else{
				flag = 0;
			}
			bigStr[i] = tmp % 2 + '0';
		}

		if(flag == 1){
			bigStr.push_back('1');
		}
		reverse(bigStr.begin(), bigStr.end());
		return bigStr;
    }
	
	// 官方解法
	string addBinary1(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

int main(){
	Solution so;
	string a = "1111";
	string b = "1111";
	string res = so.addBinary(a, b);
	cout << res << endl;
	return 0;
}